Search engine systems and devices can provide rapid searching of data tables for applications such as network packet processing, or the like. Conventional search engine systems typically rely on one or two types of memory structures to execute search operations: content addressable memories (CAMs) or random access memories (RAMs). In the case of RAMs, a data table can be searched in a sequential fashion, comparing a search key to data stored in each RAM entry. While RAM components are substantially less expensive than CAM components, such sequential search operations can take considerable time to complete.
In contrast, in a conventional CAM, a given search key can be searched against a set of data value in a parallel fashion. In the case of a ternary CAM (TCAM), each entry can include bit locations that store 0, 1 or don't-care value (X) for comparison against corresponding bits of a search key. After a parallel search on the entries of a CAM, a highest priority match can be output as a search result. Conventionally, priority can be based on physical address, and a search result can be an address or index generated by a priority encoder circuit. The parallel search capability of TCAM devices allows for search speeds well beyond those of sequential RAM approaches. Unfortunately, CAM components are considerably more expensive than RAM components, and can consume relatively large amounts of power during operation.
While CAM devices can rapidly determine the highest priority matching entry value, for some applications, determination of a single matching value is not sufficient. Instead, it may be desirable to determine the first “k” matches (k>1) or “all existing matches” within a given data set.
To better understand various features of the disclosed embodiments, conventional search engine approaches will first be described.
A first conventional approach is shown in FIGS. 12A to 12C. FIGS. 12A to 12C show entry data for a CAM device. Each CAM entry includes a table identifier value field (TID) that may identify a CAM entry as belonging to one or more particular data tables, a valid bit (V) which can include/exclude an entry from a search, and a entry value field that stores a value to be compared against a search key value KEY.
As shown in FIG. 12A, in such an approach, a first match can be found (yielding “INDEX1” as a search result). Such a matching entry can then be invalidated, by changing its valid bit from a valid state (in this case “1”) to an invalid state (in this case “0”) (FIG. 12B). A follow-on search can then be executed to look from another matching entry of lower priority (in this example, one yielding INDEXn as a search result) (FIG. 12C). In this way, a search may “invalidate” each new matching entry as it is found to thereby exclude it from further searches.
While such an approach can eventually determine all matching entries of a data set, such a conventional method may not be practical in systems where multiple threads of execution are sharing a CAM device. That is, after a search according to a first thread is executed according to one key, a subsequent search may represent a second thread, and thus utilize a different search key. In such a case, an “invalidated” matching entry would be erroneously excluded from the second thread search. Because packet processors can employ multiple threads/contexts, conventional approaches like that of FIGS. 12A to 12C are not a practical solution to such applications.
Another conventional technique is shown FIGS. 13A and 13B. FIGS. 13A and 13B show an arrangement in which table entries (e.g., CAM entries) can be connected to specialized hardware that can enable the “exploring” of portions of tables. Such hardware is referred to herein as “search-beyond” (SB) hardware. In such arrangements, an initial search can be executed with all desired entries available for search. If a match is found at location ‘j’ (FIG. 13A), a subsequent search can be executed with appropriate signals being applied to only search “beyond” location “j” (e.g., search addresses j+1 and up) (FIG. 13B).
A drawback to such arrangements is that considerable hardware may have to be added to a conventional CAM device to implement such a feature, further adding to the already high component cost.
In light of the above, it would be desirable to arrive at some way of providing for multiple match extraction searches that does not suffer from the above noted drawbacks.
It would also be desirable if such a solution could utilize existing “off-the-shelf” components, and not rely on specialized circuits, such as “search-beyond” circuits.